This invention relates generally to the reading of a multiplexed data packet stream, and more particularly to the reading of MPEG and DVD streams.
In its earliest years, video was transmitted and recorded as analog signals. However, it has long been recognized that video can also be transmitted in digital form. The advantage of digital video includes the ability to compress the digital information, error correction, and reduced signal degradation.
One technique for transmitting digital video is to break the digital information into discreet xe2x80x9cchunksxe2x80x9d or xe2x80x9cpacketsxe2x80x9d of data. These packets can be multiplexed with other packets, e.g. other video data, audio data, and other multi-media type data. Therefore, multiple signals, digitally stored in packets, can be interlaced and interwoven to provide multiple channel or multimedia content.
In FIG. 1, two signal streams are represented. A first string 10 is a video signal stream, and a second stream 12 is an audio signal stream. In its representation, the video signal stream is represented as a number of video xe2x80x9cframesxe2x80x9d 14a, 14b, 14c, 14d, 14e, 14f, 14g, and 14h. When being viewed, the frames 14a-14f are displayed or projected in rapid sequence, providing the illusion of motion.
In frame 14a, a horse 16 is galloping towards an object 18. In frames 14b, c, and d the horse 16 continues to gallop and passes the object 18. In frame 14e, the horse 16 is shot with a gun 20, and in frames 14f-14h, the horse falls to the ground, dead.
It is quite possible to store and transmit pixel information for each of the frames of 14a-14h of the video stream 10. However, this represents a tremendous amount of data, in that each frame can include millions of bites of information. For this reason, compression techniques such as MPEG, use a variety of techniques to minimize the amount of data that needs to be sent in order to reconstruct the frames 14a-14h. For example, MPEG uses a technique to reduces the amount of information sent for a new frame based upon the data that has already been sent in previous frames.
The audio stream 12 is shown here in analog form. However, if it is to be sent along with the video stream 10, it is also preferably packetized so that both the video stream 10 and the audio stream 12 can be sent along the same transmission channel. However, since the video stream 10 and the audio stream 12 must be synchronized such that, for example, when the gun 20 in frame 14e shoots the horse 16 the xe2x80x9cbangxe2x80x9d 22 of the gun is synchronized with the display of the frame 14e. This is referred to as temporal synchronization.
FIG. 1 therefore represents xe2x80x9cunpacketizedxe2x80x9d video and audio streams. In FIG. 2, the audio and video streams have been converted into a multiplex data packet stream. More particularly, the data packet stream of FIG. 2 is referred to as a xe2x80x9csystem streamxe2x80x9d of data packets 26a, 26b, 26c and 26d. In this example, packets 26a, 26b, and 26d are video data packets, and packet 26c is an audio data packet. Each of the data packets includes a header portion 28, and a payload section 30.
Generically, system streams as illustrated in FIG. 2 are used to embed digitized video streams and audio streams 12 of FIG. 1. Generally, the packets 26a-26d are of fixed size but they can also be made to have variable size.
The headers 28 store meta data, which includes such information as packet size, a time stamp, etc. The header areas 28 can also store other data or programs.
Video and audio packets are often designed so that they are large enough to accommodate more than one frame of video or audio data. Therefore, if the payload section 30 is large enough, a full frame and part of another frame can be stored within a single packet. For example, with video packet 26a all of frame 14a and a portion of frame 14b are stored in the payload section 30. In the video packet 26b, the rest of frame 14b and all of frame 14c are stored within the payload 30 of the video packet. Likewise, a marker 32 in audio packet 26c indicates that all of an audio frame 34, and a portion of the next audio frame 36 are stored within the payload section 30.
It should be noted that it is totally arbitrary how big the payload section 30 of a particular packet should be. For example, a payload section can be anywhere from one byte to one gigabyte in length. These payload sections are generally fixed, but are sometimes made variable depending on the desires of the programmer.
It should be noted that the packet size and the frame size are totally unrelated. The packet size is based upon the expectation of the data packet stream readers. For example, data packet stream readers include buffers of a given size, which expect the packets to be of a proper size to keep them full. Therefore, the encoder which creates the packets 26a-26d models the needs of the decoder or readers, and will change packet size for a given decoder type. However, since decoders or readers are standardized, the size of the packets created by the encoders also tend to be standardized.
In FIG. 3, the system stream of FIG. 2 has been transformed into a transport stream for actual transmission. The transmission stream includes a number of very small packets 38a, 38b, 38c, 38d, 38e, and 38f. Collectively, these packets 38a-38f form the video packet 26a of FIG. 2. These packets 38a-38f include their own headers 40 and payloads 42. It would be noted that the payload 42 of packet 38a includes the header 28 of the video packet 26a plus a small portion of the frame 14a of the video packet 26a. Therefore, the system stream shown in FIG. 2 is a higher level stream than the transport stream of FIG. 3. In this example, the transport level is the lowest level stream, and is the stream that is actually transmitted.
In this example, the data packet 38a-38f are rather small, e.g. 188 bytes in length. Since a frame can comprise many thousands of bytes of data, it takes a great many packets 38a-38f to carry the information for a single frame of data. For the purpose of error correction, some of the data packets 38a-38f are repeated once or twice. For example, packet 38d is a repeat of 38c, and packet 38f is a repeat of packet 38e. 
The above descriptions are somewhat conceptual in that they illustrate actual image frames being sent. However, as is well known to those skilled in the art, compression technology such as MPEG do not send pictures, per se, but send motion vectors which indicate changes from previous frames. However, periodically, the whole frame is sent in what is known as a I frame. Other frames may have part of a picture, but with pointers to an I frame or another frame.
The sequential transmission of a large number of the data packets 38a-38f of FIG. 3 comprise the transport stream 44. Once the transport stream has been received, it must be decoded or xe2x80x9creadxe2x80x9d in order to recover the original data.
In FIG. 4, a conceptual representation of a reader takes the transport stream 44 and puts it through an input/output (I/O) process 46 to fill a xe2x80x9cpipelinexe2x80x9d or buffer 48. The portion 50 of the buffer indicates the filled region, and the portion 52 of the buffer indicates that portion of the buffer that can be filled with new data from the transport stream 44. The I/O process 46 can determine the boundary line or pointer 54 between the filled and the unfilled regions of the buffer 48, and can determine when the buffer 48 is sufficiently low enough that additional data from the transport stream 44 should be entered into the buffer. The data within the buffer 48 moves toward the base 56 of the buffer as indicated by arrow 58 where a parcer process 60 reads a segment 62 of the buffer and reconstitutes, for example, the frame 64.
It should be noted that the conventional reading process 66 of the prior art is a destructive reading process in that the data slides towards the base 56 of the buffer 48 and therefore overrides the portion 62 that has already been read by the parser 60. Therefore, as the process 66 gathers data, the original data is lost by being overwritten by new data to be read. As a consequence, there is no practical way to read backwards in a multiplex data packet stream of the prior art.
It will therefore be appreciated that readers for multiplexed data packet streams of the prior art have very limited abilities to transfer the data packet stream. In particular, they have almost no ability to accurately traverse a data packet in the reverse direction due to the movement of the data through the buffers through the reading process.
The present invention is preferably implemented with a set of C++ classes designed to make MPEG streams (or other data packet streams such as DVD streams) easier to work with. They accomplish this by making useful data abstractions, enabling MPEG software developers to write cleaner, better factored code.
The present invention permits a user to seek to an arbitrary location in an MPEG (or other) system stream, and provides a tool to xe2x80x9csync upxe2x80x9d on the system stream such that the nearest system stream object is returned. The search used to locate this object is bi-directional, and is robust with respect to end of stream and beginning of stream boundary conditions. This feature of the present invention is typically used to seek a location in the stream corresponding to an approximate time calculated from the stream bit rate.
Once the arbitrary system stream object is obtained, the system stream can be considered in an entirely new fashion: as a doubly-linked list of objects. This permits a user to can scan forwards and backwards in the system stream by traversing object links. The present invention uses an LRU scheme to keep objects in memory while they are in use and re-uses memory as new places in the stream are sought. In consequence, objects are referenced by absolute byte position in the stream, allowing the present invention to reclaim memory. Multiple disjoint locations may be accessed in the system stream xe2x80x9cvirtual linked list.xe2x80x9d
Since the present invention also uses an LRU scheme for low level I/O buffering, an object may sometimes straddle a page boundary; the object is not in contiguous memory. For this reason, The present invention provides tools for seamless access to the data in an object. Also, the number of pages and the size of the pages in the low level IO LRU paging buffer can be controlled by the user.
The present invention further provides a tool for locating the nearest packet with a specified stream ID. Therefore, forward searches, backward searches, or bi-directional searches are possible in the system stream virtual linked list.
Once a user has a reference to a packet with the specified stream ID, the present invention allows the creation of a new stream which contains only data from the payload section of packets homogenous with the packet. This essentially de-multiplexes the system stream. The homogenous stream is pure video or audio, depending on the stream ID that was selected. The streams origin is set at the first payload byte of the start packet. A user can seek forwardly with positive offsets, or backwardly with negative offsets.
In consequence, a user can seek arbitrarily in the homogenous stream. The present invention allows a user to view a homogenous stream as a virtual linked list, as described above. The objects worked with at this level are video objects. A user can traverse the virtual linked list forwardly and backwardly to find a particular video object. A user can further interrogate a video object to find out what system stream packet it starts in. This is useful for determining to which frame the packet""s DTS/PTS time stamp information applies.
The present invention therefore provides tools for seamless access to the data in a video object, which may straddle packet boundaries in the system stream, or low level IO page boundaries, and further provides tools for accessing data at the bit level, and for performing forward and backward seeks at the bit level. It will therefore be appreciated that the present invention is a useful addition for many MPEG and other data stream applications.
These and other advantages of the present invention will become apparent to those skilled in the art upon a reading of the following descriptions of the invention and a study of the several figures of the drawing.